package E_2024;

import java.util.Arrays;

/*
     MELON有一堆精美的雨花石(数量为n，重量各异)，准备送给S和W。
     MELON希望送给俩人的雨花石重量一致，请你设计一个程序帮MELON确认是否能将雨花石平均分配。
输入描述
    第1行输入为雨花石个数: n，0 < n < 31.
    第2行输入为空格分割的各雨花石重量: m[0] m[1] ..... m[n - 1]， 0 < m[k] < 1001
    不需要考虑异常输入的情况。
输出描述
    如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等:如果不能均分，则输出-1。
示例1：
    输入
    4
    1 1 2 2
    输出
    2
    说明
    输入第一行代表共4颗雨花石，第二行代表4颗雨花石重量分别为1、1、2、2。均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，所以输出2。
 */
public class E_200_27 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{1,1,2,2}));
        System.out.println(ans(new int[]{1,1,1,1,1,9,8,3,7,10}));
    }
    public static int ans(int[] arr){
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2 != 0) return -1;
        int mid = sum / 2;
        Arrays.sort(arr);
        int[][] dp = new int[arr.length + 1][mid + 1];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i < arr.length; i++) {
            int sco = arr[i];
            for (int j = 1; j <= mid; j++) {
                if (j >= sco)
                    dp[i+1][j] = Math.min(dp[i][j-sco]+1,dp[i][j]);
                else
                    dp[i+1][j] = dp[i][j];
            }
        }
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        return dp[arr.length][mid];
    }
}
